package ShortestPath;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class MinimumGeneticMutation {
    public int minMutation(String startGene, String endGene, String[] bank) {
        // 辅助数组
        char[] change = { 'A', 'C', 'G', 'T' };

        // 用哈希表(Set)来标记已经搜索过的状态
        Set<String> visit = new HashSet<>();

        // 统计基因库里面的序列
        // 每层节点若是存在于 bank 中, 才算有效序列
        Set<String> bankSet = new HashSet<>();
        for (String s : bank) {
            bankSet.add(s);
        }

        if(startGene.equals(endGene)) {
            // 如果初始序列和最终序列相同, 没必要变化了
            return 0;
        }

        if(!bankSet.contains(endGene)) {
            // 如果基因库中都不存在最终序列
            return -1;
        }

        // 用队列保存符合要求的字符串
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        visit.add(startGene);

        // 记录路径步伐
        int step = 0;

        while (!queue.isEmpty()) {
            // 每次进入循环, 说明要往外扩一层, 即向前走一步, 因此:
            step++;
            // 记录每层的节点个数
            int size = queue.size();
            while (size-- != 0) {
                // 取出当前点
                String point = queue.poll();

                // 遍历下一层节点
                // 8: 序列固定长度为 8
                for (int i = 0; i < 8; i++) {
                    // 每次只能修改一个字符, 因此每次只能基于每层原节点的每个字符进行修改
                    char[] tmp = point.toCharArray();
                    for (int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        String nextNode = new String(tmp);
                        if (bankSet.contains(nextNode) && !visit.contains(nextNode)) {
                            // 如果基因库中存在, 且没有被访问过的序列才能入队列
                            if (endGene.equals(nextNode)) {
                                // 如果变化后已经等于 end 序列, 直接返回 step
                                return step;
                            }
                            queue.offer(nextNode);
                            visit.add(nextNode);
                        }
                    }
                }
            }
        }

        // 走到这说明没有出口
        return -1;
    }
}
